在 C++ 中，管理容器增长是一场在 大小 （当前元素数量）和 容量 （预留内存）之间的权衡。对于像 vector 和 string这样的连续容器来说，达到容量上限会触发 重新分配：系统会寻找更大的内存块，将所有元素移动过去，并销毁旧的内存块。这是一个代价高昂的 $O(n)$ 操作，会导致 迭代器失效——你对旧元素的指针将变成“悬空”指针，非常危险。
1. 扩展策略
为了避免频繁的重新分配， vector 实现通常会预先分配一段“缓冲区”空间。使用 c.reserve(n) 命令可显式设置最小容量而不添加元素，而 c.shrink_to_fit() 则是一个非强制性的请求，要求将多余的内存归还给操作系统。
2. resize 与 reserve 的区别
虽然 reserve reserve 只影响缓冲区， resize(n) resize(n) 则会主动改变容器的逻辑。通过 resize 缩小容器会删除元素，而扩展则会添加默认初始化的值。
⚠️ 警告： 如果
resize 缩小容器时，指向被删除元素的迭代器将失效。如果扩展导致重新分配， 所有 迭代器都将失效。main.py
TERMINALbash — 80x24
> Ready. Click "Run" to execute.
>
QUESTION 1
Exercise 9.34: Predict the behavior of this loop: while (iter != vi.end()) { if (*iter % 2) iter = vi.insert(iter, *iter); ++iter; }
It duplicates all odd numbers once and finishes.
It results in an infinite loop if an odd number is found.
It skips all odd numbers.
It causes a compilation error because of iterator types.
✅ Correct!
This is an infinite loop. vi.insert(iter, *iter) inserts before the current element and returns an iterator to the NEW element. The ++iter then moves back to the original odd element, repeating the process forever.❌ Incorrect
Analyze the return value of insert: it points to the newly inserted element. Incrementing once just puts you back on the original element you just processed.QUESTION 2
Exercise 10.10: Why don't generic algorithms like find or sort change the size of containers?
They operate on iterators, which provide no interface to add/remove container memory.
Changing size would be too slow for generic code.
The C++ standard forbids algorithms from using memory.
Algorithms only work on fixed-size arrays.
✅ Correct!
Algorithms are decoupled from containers. They only see iterators and can only modify the values the iterators point to; they cannot call container-specific members like push_back or erase.❌ Incorrect
Recall the 'Iterator Bridge' concept: algorithms use iterators to remain container-agnostic.QUESTION 3
Given vec has 25 elements, what happens if we call vec.resize(100) then vec.resize(10)?
Size becomes 100, then drops to 10; capacity likely stays at 100 throughout.
Size becomes 100, then 10; capacity drops to 10 immediately.
The program crashes on the second resize.
The elements from index 10-99 are moved to a temporary buffer.
✅ Correct!
resize(100) adds 75 default-initialized elements. resize(10) destroys the last 90 elements, but the allocated capacity remains 100 unless shrink_to_fit is called.❌ Incorrect
Resize shrinks the 'size', but capacity does not shrink automatically to save performance.QUESTION 4
What restriction is placed on the element type when calling the single-argument version of resize?
It must be a primitive type (int, double, etc.).
It must have a default constructor.
It must have a copy constructor.
It cannot be a const type.
✅ Correct!
Since resize(n) creates new elements to reach size n, those elements must be initialized using a default constructor.❌ Incorrect
If we don't provide an initial value, the container must know how to build a 'default' one.QUESTION 5
Exercise 10.39: What kind of iterator does a list have versus a vector?
List: Forward; Vector: Random-access
List: Bidirectional; Vector: Random-access
Both have Random-access iterators.
List: Output; Vector: Input
✅ Correct!
std::list is a doubly-linked list supporting bidirectional movement. std::vector is an array supporting pointer-like arithmetic (Random-access).❌ Incorrect
Can you do 'it + 5' on a list? No, which means it isn't random-access.Case Study: Safe Iterator Loops
Managing Growth in Real-time Applications
You are processing a vector of integers. For every odd number, you must duplicate it. You also need to maintain efficiency and avoid segmentation faults caused by container reallocation during the loop.
Q
1. Re-implement Exercise 9.34 correctly to avoid the infinite loop and handle iterator invalidation.
Solution:
To fix the loop: iter = vi.begin(); while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); iter += 2; } else { ++iter; } } This works because insert returns the iterator to the new element; we advance past both the new and original elements to find the next candidate.
To fix the loop: iter = vi.begin(); while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); iter += 2; } else { ++iter; } } This works because insert returns the iterator to the new element; we advance past both the new and original elements to find the next candidate.
Q
2. Rewrite the duplicate word elimination logic from § 10.2.3 to use a list instead of a vector. What changes?
Solution:
Since list does not support random-access, we cannot use generic sort. We must use lst.sort() and lst.unique() member functions. Unlike the vector version, lst.unique() actually removes elements from the list, changing its size immediately without needing a separate erase call.
Since list does not support random-access, we cannot use generic sort. We must use lst.sort() and lst.unique() member functions. Unlike the vector version, lst.unique() actually removes elements from the list, changing its size immediately without needing a separate erase call.
Q
3. Exercise 10.19: Rewrite the biggies logic to use stable_partition instead of find_if to maintain original order.
Solution:
auto wc = stable_partition(words.begin(), words.end(), [sz](const string &s) { return s.size() >= sz; }); This reorders the container such that all elements meeting the criteria come first, returning an iterator to the first element that does NOT meet the criteria.
auto wc = stable_partition(words.begin(), words.end(), [sz](const string &s) { return s.size() >= sz; }); This reorders the container such that all elements meeting the criteria come first, returning an iterator to the first element that does NOT meet the criteria.